﻿namespace Leetcode.N0310;
public class Solution
{
    public IList<int> FindMinHeightTrees(int n, int[][] edges)
    {
        if (n <= 1)
        {
            return new List<int>() { 0 };
        }

        var nodeEdges = new List<int>[n];
        var nodeEdgesCount = new int[n];

        for (var i = 0; i < n; i++)
        {
            nodeEdges[i] = new List<int>();
        }

        foreach (var item in edges)
        {
            nodeEdges[item[0]].Add(item[1]);
            nodeEdges[item[1]].Add(item[0]);
            nodeEdgesCount[item[0]]++;
            nodeEdgesCount[item[1]]++;
        }

        var leafNodes = new Queue<int>();
        for (var i = 0; i < n; i++)
        {
            if (nodeEdgesCount[i] == 1)
            {
                leafNodes.Enqueue(i);
            }
        }

        var result = new List<int>();
        while (leafNodes.Count > 0)
        {
            var leafNodeCount = leafNodes.Count;
            result.Clear();

            for (var i = 0; i < leafNodeCount; i++)
            {
                var node = leafNodes.Dequeue();
                result.Add(node);
                foreach (var next in nodeEdges[node])
                {
                    nodeEdgesCount[next]--;
                    if (nodeEdgesCount[next] == 1)
                    {
                        leafNodes.Enqueue(next);
                    }
                }
            }
        }

        return result;
    }
}
